package com.jxb.three;

/**
 * 获取多数元素：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。
 */
public class MajorityElement_169 {

    public static void main(String[] args) {

    }

    /**
     * 通过Boyer-Moore 投票算法
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int countNumber = nums[0];
        int count = 1;
        for (int i = 1; i< nums.length;i++) {
            if (count == 0) {
                countNumber = nums[i];
                count = 1;
            }else {
                if (nums[i] != countNumber) {
                    count--;
                }else {
                    count++;
                }
            }
        }
        return countNumber;
    }







}
